
from Code_Link_02 import ListNode
from Code_Link_02 import printLink

''' 
https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/
链表相交，如下相交点为c3，如没有相交点，返回null
A: a1 -> a2 ->    c1 ->c2 ->c3
B: b1 ->b2 ->b3-> c1 ->c2 ->c3
方法：从AB相同长度位置向后遍历，首先算出AB长度
'''
def l0207(headA:ListNode,headB:ListNode):
    dummyA = ListNode(next=headA)
    dummyB = ListNode(next=headB)
    sizeA = sizeB = s = 0
    shortA = True #默认A短
    while dummyA.next or dummyB.next:
        if dummyA.next:
            dummyA = dummyA.next
            sizeA += 1
        if dummyB.next:
            dummyB = dummyB.next
            sizeB += 1
    print(sizeA,sizeB)
    if sizeA > sizeB:shortA = False #A长B短，默认A短
    s = abs(sizeB -sizeA)
    A = ListNode(next=headA)
    B = ListNode(next=headB)
    if shortA:
        while s>0:
            B = B.next
            s -= 1
        while B:
            if B.next == A.next:
                return B.next
            B = B.next
            A = A.next
    else:
        while s>0:
            A = A.next
            s -= 1
        while B:
            if B.next == A.next:
                return B.next
            B = B.next
            A = A.next
    printLink(A)
    printLink(B)
    return None

def l0207_1(headA:ListNode,headB:ListNode):
    cur = headA
    sizeA = sizeB = 0
    while cur:
        cur = cur.next
        sizeA += 1
    cur = headB
    while cur:
        cur = cur.next
        sizeB += 1
    print(sizeA,sizeB)
    curA,curB = headA,headB
    if sizeA > sizeB: #确保A短 B长
        curA,curB = curB,curA
        sizeA,sizeB = sizeB,sizeA
    for i in range(sizeB-sizeA):
        curB = curB.next #确保B 和 A 在同一起跑线上
    while curA:
        if curA == curB:
            return curA
        else:
            curA = curA.next
            curB = curB.next

    return None

if __name__ == '__main__':
    c2 = ListNode(7)
    c1 = ListNode(6,c2)
    a3 = ListNode(5,c1)
    a2 = ListNode(4,a3)
    a1 = ListNode(3,a2)
    #link3 = ListNode(3)
    b2 = ListNode(2,c1)
    b1 = ListNode(1,b2)
    #printLink(link1)
    res = l0207_1(a1,b2)
    printLink(res)

    #l206(link6)
    pass